package com.sakura.二叉树;

public class Code110_平衡二叉树 {

    
      // Definition for a binary tree node.
      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

    public boolean isBalanced(TreeNode root) {
          if (root == null) return true;
        return getHeight(root) != -1;
    }

    /**
     * 求当前树的高度  使用后序遍历：后序遍历可以从左右节点中获取信息，然后返回给父节点
     *   明确递归函数的参数和返回值
     *      参数：当前节点 返回值：当前树的高度
     *   明确终止条件
     *      node == null return 0
     *   明确单层递归的逻辑
     *      遍历左右子树，拿到对应的高度，如果高度返回的是-1，则不是平衡二叉树，直接返回-1
     *      如果左右子树高度差大于1，则不是平衡二叉树，直接返回-1
     *      否则返回当前树的高度
     * @param node
     * @return 返回-1代表不是平衡二叉树
     */
    private int getHeight(TreeNode node) {
        if (node == null) return 0;
        int left = getHeight(node.left);
        if (left == -1) return -1;
        int right = getHeight(node.right);
        if (right == -1) return -1;
        if (Math.abs(left - right) > 1) {
            return -1;
        } else {
            return Math.max(left, right) + 1;
        }
    }
}
